from 并查集.unionFind import unionFind
#力扣200题
grid = [
  ["0","0","0","0","0"],
  ["0","0","0","0","0"],
  ["0","0","0","0","0"],
  ["0","0","0","0","1"]
]

def gridIndex(i,j):
    return i * len(grid[0]) + j
def islandCount(root):
    count = 0
    for i in range(len(root)):
        if root[i] == i and grid[i//len(grid[0])][i%len(grid[0])] == "1":
            count += 1
    return count
if __name__ == '__main__':
    gridUF = unionFind(grid)
    for i in range(len(grid)):
        for j in range(len(grid[i])):#对grid中的元素进行遍历
            if i < len(grid) - 1 and grid[i+1][j] == "1" and grid[i][j] == "1":#右侧元素为1则
                gridUF.union(gridIndex(i,j),gridIndex(i+1,j))
            if j < len(grid[i]) - 1 and grid[i][j+1] == "1" and grid[i][j] == "1":#下侧元素为1则union
                gridUF.union(gridIndex(i,j),gridIndex(i,j+1))
    print(islandCount(gridUF.root))